class Solution(object):
    def countDigitOne(self, n):
        """
        :type n: int
        :rtype: int
        """
        s = str(n)
        k = len(s)
        num = [0] * k
        DP = [0] * k
        for i in range(k):
            num[i] = int(s[i])
        for i in range(1, k):
            DP[i] = 10 * DP[i - 1] + 10 ** (i - 1)
        DP.reverse()
        total = 0
        for i in range(k):
            total += num[i] * DP[i]
            if num[i] > 1:
                total += 10 ** (k - 1 - i)
            else:
                if num[i] == 1:
                    if i != k - 1:
                        total += int(s[i + 1:]) + 1
                    else:
                        total += 1
        return total


data = Solution()
n = 13
print(data.countDigitOne(n))
